package homework.exp05;

import java.io.File;
import java.io.FileInputStream;
import java.util.Scanner;

/**
 * 递推问题的终结解决方案，矩阵快速幂实现
 */
public class G {
    static Scanner cin = null;

    static {
        try {
            cin = new Scanner(new FileInputStream(new File("G.in")));
        } catch (Exception e) {
            cin = new Scanner(System.in);
        }
    }

    public static void main(String[] args) {
        Matrix m = new Matrix(new long[][]{{1, 1}, {1, 0}});
        while (cin.hasNext()) {
            int n = cin.nextInt();
            if (n == -1) break;
            if (n == 0) {
                System.out.println(0);
                continue;
            }
            System.out.println(m.pow(n - 1).data[0][0]);
        }
    }

}

class Matrix {
    @Override
    public String toString() {
        return String.format("%d %d\n%d %d", data[0][0], data[0][1], data[1][0], data[1][1]);
    }

    final static Matrix ZERO = new Matrix();
    final static Matrix UNIT = new Matrix(new long[][]{{1, 0}, {0, 1}});
    final static int MOD = 10000;
    final int row = 2, col = 2;
    long[][] data = new long[row][col];

    public Matrix(long[][] ints) {
        this.data = ints;
    }

    public Matrix() {
        this(new long[2][2]);
    }

    Matrix mul(Matrix that) {
        Matrix C = new Matrix();
        C.data[0][0] = (this.data[0][0] * that.data[0][0] % MOD + this.data[0][1] * that.data[1][0] % MOD) % MOD;
        C.data[0][1] = (this.data[0][1] * that.data[1][1] % MOD + this.data[0][0] * that.data[0][1] % MOD) % MOD;
        C.data[1][0] = (this.data[1][0] * that.data[0][0] % MOD + this.data[1][1] * that.data[1][0] % MOD) % MOD;
        C.data[1][1] = (this.data[1][0] * that.data[0][1] % MOD + this.data[1][1] * that.data[1][1] % MOD) % MOD;

        return C;

    }

    Matrix pow(int n) {
        if (n == 0) return UNIT;
        if (n == 1) return this;
        if ((n & 1) == 0) {
            return this.mul(this).pow(n / 2);
        }
        return this.mul(this).pow(n / 2).mul(this);
    }
}